package com.sort;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author zhongyi_yang
 */
public class HeapSort {
	/**
	 * 堆排序
	 *
	 * @param dataWraps
	 */
	public static void heapSort(DataWrap[] dataWraps) {
		System.out.println("开始排序：");
		int arrayLength = dataWraps.length;
		// 循环建堆
		for (int i = 0; i < arrayLength - 1; i++) {
			// 建堆
			buildMaxHeap(dataWraps, arrayLength - 1 - i);
			// 交换堆顶和最后一个元素
			swap(dataWraps, 0, arrayLength - 1 - i);
			System.out.println(Arrays.toString(dataWraps));
		}
	}

	// 对dataWraps数组从0到lastIndex建大顶堆
	private static void buildMaxHeap(DataWrap[] dataWraps, int lastIndex) {
		// 从lastIndex处节点（最后一个节点）的父节点开始
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			// k保存当前正在判断的节点
			int k = i;
			// 如果当前K节点的子节点存在
			while (k * 2 + 1 <= lastIndex) {
				// k节点的左子结点的索引
				int biggerIndex = 2 * k + 1;
				// 如果biggerIndex小于lastIndex，即biggerIndex+1
				// 代表k节点的右子节点存在
				if (biggerIndex < lastIndex) {
					// 如果右子节点的值比较大
					if (dataWraps[biggerIndex]
							.compareTo(dataWraps[biggerIndex + 1]) < 0) {
						// biggerIndex总是记录较大子节点的索引
						biggerIndex++;
					}
				}
				// 如果k节点的值小于其较大子节点的值
				if (dataWraps[k].compareTo(dataWraps[biggerIndex]) < 0) {
					// 交换它们
					swap(dataWraps, k, biggerIndex);
					// 将biggerInde赋给k，开始while循环的下一次循环
					// 重新保证k节点的值大于其左右节点的值
					k = biggerIndex;
				} else {
					break;
				}
			}
		}
	}

	// 交换dataWraps数组中i、j两个索引出的元素
	private static void swap(DataWrap[] data, int i, int j) {
		DataWrap tmpDataWrap = data[i];
		data[i] = data[j];
		data[j] = tmpDataWrap;
	}

	public static void main(String[] args) {
		DataWrap dataWrap[] = {new DataWrap(21, ""), new DataWrap(30, ""),
				new DataWrap(49, ""), new DataWrap(30, "*"),
				new DataWrap(21, "*"), new DataWrap(16, ""),
				new DataWrap(9, "")};
		System.out.println("排序前：" + Arrays.toString(dataWrap));
		heapSort(dataWrap);
		System.out.println("排序后：" + Arrays.toString(dataWrap));
	}
}
